package cn.chen.算法.排序;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 归并排序：将数组进行分组，利用递归，将分组后的每一组都进行分组，然后将组进行合拢，两两合拢，合拢之后的组是有序的。以此类推，最后的一组就是有序的序列了。
 */
public class MergeSort {

    static int[] temp;

    public static void main(String[] args){
//        int []a={8,5,4,1,-2,6,9,12,0};
        int []a=new int[80000];
        for(int i=0;i<a.length;i++){

            a[i]= (int) (Math.random()*800000);
        }
        SimpleDateFormat format=new SimpleDateFormat("yyyy-MM-dd hh:mm:ss");
        String start = format.format(new Date());
        System.out.println("开始时间："+start);
        temp=new int[a.length];    // 辅助数组


        mergeSort(a,0,a.length-1);

        String end = format.format(new Date());
        System.out.println("结束时间："+end);

    }

    /**
     *
     * @param a     要分组的组
     * @param start 该组的开始索引
     * @param end   该组的结束索引
     */
    public static void mergeSort(int [] a,int start,int end){

        if(start<end){

            int min=(start+end)/2;
            mergeSort(a,start,min); // 递归，将该组进行分组
            mergeSort(a,min+1,end); // 递归，将该组进行分组

            merge(a,start,min,end); // 将start~min这一组和min+1~end这一组 这两组进行一个合并，合并需要使用到一个辅助数组
        }
    }
    // 合并两组的方法，根据索引来分组，从start到min是一组，从min+1到end是一组，每一组都是有序的

    /**
     *
     * @param a     要排序的数组
     * @param start 第一组的开始索引
     * @param min   第一组的结束索引，min+1就是第二组的开始索引
     * @param end   第二组的结束索引
     */
    private static void merge(int[] a, int start, int min, int end) {

        // 将a数组中的数据复制到temp（辅助数组）中
        for(int i=start;i<=end;i++)
            temp[i]=a[i];

        int i=start,j=min+1,k=i;    // k就是用来作为a数组的索引的，a数组中添加一个数据就将k++,k从start开始,到end结束

        for(;i<=min&&j<=end;k++){   // 开始循环遍历temp数组，索引从i和j开始。

            if(temp[i]<temp[j]) // 如果前面数据小，就将前面数据保存在a数组中
                a[k]=temp[i++];
            else
                a[k]=temp[j++]; // 如果后面数据小，就将后面数据保存在a数组中
        }
        // 将前后两组中剩下的数据保存在a数组中，只可能有一组剩下数据
        while (i<=min)
            a[k++]=temp[i++];
        while (j<=end)
            a[k++]=temp[j++];
    }
}
